package com.epam.training.concurrency.first.task2;

import java.util.logging.Level;
import java.util.logging.Logger;

import com.epam.training.concurrency.first.task3.CircularBuffer;

/**
 * 
 * @author Bogdan
 *
 */
public class MultithreadMergeSort {

	public static final int THRESHOLD = 500;

	/**
	 * 
	 * @param value
	 * @param array
	 * @param lowIndex
	 * @param highIndex
	 * @return
	 */
	private int binarySearch(int value, int[] array, int lowIndex, int highIndex) {
		int low = lowIndex;
		int high = Math.max(lowIndex, highIndex + 1);

		while (low < high) {
			int mid = (low + high) >>> 1;
			if (value <= array[mid]) {
				high = mid;
			} else {
				low = mid + 1;
			}
		}

		return high;
	}

	/**
	 * 
	 * @param arrayIn
	 * @param lowIndex1
	 * @param highInex1
	 * @param lowIndex2
	 * @param highIndex2
	 * @param arrayOut
	 * @param lowIndex3
	 * @throws InterruptedException
	 */
	private void parallelMerge(int[] arrayIn, int lowIndex1, int highIndex1,
			int lowIndex2, int highIndex2, int[] arrayOut, int lowIndex3)
			throws InterruptedException {
		int n1 = highIndex1 - lowIndex1 + 1;
		int n2 = highIndex2 - lowIndex2 + 1;

		if (n1 < n2) {
			int tmp = lowIndex1;
			lowIndex1 = lowIndex2;
			lowIndex2 = tmp;

			tmp = highIndex1;
			highIndex1 = highIndex2;
			highIndex2 = tmp;

			tmp = n2;
			n2 = n1;
			n1 = tmp;
		}

		if (n1 == 0)
			return;
		else {
			int q1 = (lowIndex1 + highIndex1) >>> 1;
			int q2 = binarySearch(arrayIn[q1], arrayIn, lowIndex2, highIndex2);
			int q3 = lowIndex3 + (q1 - lowIndex1) + (q2 - lowIndex2);

			arrayOut[q3] = arrayIn[q1];

			Thread thread = null;

			if (n1 < THRESHOLD && n2 < THRESHOLD) {
				thread = new Thread(new MergeThread(arrayIn, lowIndex1, q1 - 1,
						lowIndex2, q2 - 1, arrayOut, lowIndex3));
				thread.start();
			} else {
				parallelMerge(arrayIn, lowIndex1, q1 - 1, lowIndex2, q2 - 1,
						arrayOut, lowIndex3);
			}

			parallelMerge(arrayIn, q1 + 1, highIndex1, q2, highIndex2,
					arrayOut, q3 + 1);
			if (thread != null) {
				thread.join();
			}
		}
	}

	/**
	 * 
	 * @param arrayIn
	 * @param lowIndex
	 * @param highIndex
	 * @param arrayOut
	 * @param startIndex
	 * @throws InterruptedException
	 */
	public void sort(int[] arrayIn, int lowIndex, int highIndex,
			int[] arrayOut, int startIndex) throws InterruptedException {
		int n = highIndex - lowIndex + 1;
		if (n == 1) {
			arrayOut[startIndex] = arrayIn[lowIndex];
		} else {
			int[] T = new int[n];
			int q = (lowIndex + highIndex) / 2;
			int q1 = q - lowIndex;

			Runnable threadSort = null;

			if (n < THRESHOLD) {

				threadSort = new Thread(new SortThread(arrayIn, lowIndex, q, T,
						0));
				((Thread) threadSort).start();
			} else {
				sort(arrayIn, lowIndex, q, T, 0);
			}
			sort(arrayIn, q + 1, highIndex, T, q1 + 1);

			if (threadSort != null) {
				((Thread) threadSort).join();
			}
			parallelMerge(T, 0, q1, q1 + 1, n - 1, arrayOut, startIndex);

		}
	}

	private class SortThread implements Runnable {

		int[] inputArray;
		int low;
		int high;
		int[] outArray;
		int s;

		@Override
		public void run() {
			try {
				sort(inputArray, low, high, outArray, s);
			} catch (InterruptedException e) {
				Logger.getLogger(CircularBuffer.class.getName()).log(
						Level.SEVERE, null, e);
			}
		}

		SortThread(int[] inputArray, int low, int high, int[] outArray, int s) {
			this.inputArray = inputArray;
			this.low = low;
			this.high = high;
			this.outArray = outArray;
			this.s = s;
		}
	}

	/**
	 * 
	 * @author Bogdan
	 *
	 */
	private class MergeThread implements Runnable {

		private int[] array;
		int low1;
		int high1;
		int low2;
		int high2;
		int[] outArray;
		int low3;

		MergeThread(int[] array, int low1, int high1, int low2, int high2,
				int[] outArray, int low3) {
			this.array = array;
			this.low1 = low1;
			this.high1 = high1;
			this.low2 = low2;
			this.high2 = high2;
			this.outArray = outArray;
			this.low3 = low3;
		}

		@Override
		public void run() {
			try {
				parallelMerge(array, low1, high1, low2, high2, outArray, low3);
			} catch (InterruptedException e) {
				Logger.getLogger(CircularBuffer.class.getName()).log(
						Level.SEVERE, null, e);
			}
		}
	}
}
